package com.tyrone.algorithm.graph;

import com.tyrone.algorithm.linear.Queue;

/**
 * 有向图
 */
public class Digraph {
    private final int V;                // 记录顶点数量
    private int E;                      //记录边数量
    private Queue<Integer>[] adj;                // 邻接表

    public Digraph(int V){
        this.V=V;
        this.E=0;
        this.adj=new Queue[V];
        for (int i = 0; i < adj.length; i++) {
            adj[i]=new Queue<Integer>();
        }
    }
    /***
     * 获取图中顶点的数量
     * @return
     */
    public int V(){
        return V;
    }

    /**
     * 获取图中边的数量
     * @return
     */
    public int E(){
        return E;
    }

    /**
     * 向有向图中添加一条边 v->w
     * @param v
     * @param w
     */
    public void addEdge(int v,int w){
        adj[v].enqueue(w);
        E++;
    }

    /**
     *
     * @param v
     * @return
     */
    public Queue<Integer> adj(int v){
        return adj[v];
    }

    /**
     *
     * @return
     */
    private Digraph reverse(){
        Digraph r = new Digraph(V);
        for (int v = 0; v < V; v++) {
            for (Integer w : adj[v]) {
                r.addEdge(w,v);
            }
        }
        return r;
    }
}
